﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace November {
    class AlphaNumericComparer : IComparer<String> {
        public Int32 Compare(String x, String y) {
            int xMarker = 0, yMarker = 0;
            int xLength = x.Length, yLength = y.Length;

            while (xMarker < xLength && yMarker < yLength) {
                String xChunk = GetNextChunk(x, xLength, xMarker);
                xMarker += xChunk.Length;

                String yChunk = GetNextChunk(y, yLength, yMarker);
                yMarker += yChunk.Length;

                int result = 0;

                bool xNumeric = Char.IsDigit(xChunk[0]);
                bool yNumeric = Char.IsDigit(yChunk[0]);

                if (xNumeric && yNumeric) {
                    int xChunkLength = xChunk.Length;
                    result = xChunkLength - yChunk.Length;
                    if (result != 0) { return result; }

                    for (int i = 0; i < xChunkLength; i++) {
                        result = xChunk[i] - yChunk[i];
                        if (result != 0) { return result; }
                    }
                }
                else if (xNumeric) { return -1; }
                else if (yNumeric) { return +1; }
                else {
                    result = String.Compare(xChunk, yChunk);
                    if (result != 0) { return result; }
                }
            }
            return xLength - yLength;
        }

        private static String GetNextChunk(String source, Int32 length, Int32 marker) {
            StringBuilder chunkBuilder = new StringBuilder();
            Char next = source[marker++];
            chunkBuilder.Append(next);

            if (Char.IsDigit(next)) {
                while (marker < length) {
                    next = source[marker++];
                    if (!Char.IsDigit(next)) { break; }
                    chunkBuilder.Append(next);
                }
            }
            else {
                while (marker < length) {
                    next = source[marker++];
                    if (Char.IsDigit(next)) { break; }
                    chunkBuilder.Append(next);
                }
            }
            return chunkBuilder.ToString();
        }
    }
}
